package com.cat.DataStructure04;

/**
 *   @description https://leetcode.cn/problems/longest-palindromic-subsequence-after-at-most-k-operations/
 *   @author 曲大人的喵
 *   @create 2025/11/25 18:41
 *   @since JDK17
 */

public class Solution10 {
    static int N = 201;
    static int[][][] dp = new int[N][N][N];
    int get(char a, char b, int k) {
        int p = Math.min((a - b + 26) % 26, (b - a + 26) % 26);
        return k >= p ? k - p : -1;
    }
    int dfs(char[] s, int l, int r, int k) {
        if (l > r) {
            return 0;
        }
        if (dp[l][r][k] != -1) {
            return dp[l][r][k];
        }
        if (l == r) {
            return 1;
        }
        int ans = 0;
        if (s[l] == s[r]) {
            ans = 2 + dfs(s, l + 1, r - 1, k);
        } else {    // 不相等
            ans = dfs(s, l + 1, r - 1, k);  // 左右两个都不要
            int cost = get(s[l], s[r], k);  // 费用
            if (cost >= 0) {    // 可以转
                ans = Math.max(ans, dfs(s, l + 1, r - 1, cost) + 2);
            }
            ans = Math.max(ans, Math.max(dfs(s, l + 1, r, k), dfs(s, l, r - 1, k)));    // 要一个
        }
        dp[l][r][k] = ans;
        return ans;
    }
    public int longestPalindromicSubsequence(String s, int k) {
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                for (int l = 0; l <= k; l++) {
                    dp[i][j][l] = -1;
                }
            }
        }

        return dfs(arr, 0, arr.length - 1, k);
    }
}